
class Solution {
    int result = Integer.MAX_VALUE;
    public int minimumIncompatibility(int[] nums, int k) {
        
        Arrays.sort(nums);
        Bucket[] buckets = new Bucket[k];
        for (int i = 0; i < k; ++i)
            buckets[i] = new Bucket();
        int bucketSize = nums.length / k;
        dfs(nums, 0, 0, buckets, bucketSize);
        return result == Integer.MAX_VALUE ? -1 : result;
        
    }
    
    private void dfs (int[] nums, int index, int sum, Bucket[] buckets, int bucketSize){
        
        if (index == nums.length){
            result = sum;
            return;
        }
        int num = nums[index];
        int currentSize = bucketSize;
        
        for (Bucket bucket : buckets){
            if (bucket.size == currentSize || bucket.max == num)
                continue;
                
            currentSize = bucket.size;
            int delta = currentSize == 0? 0: num - bucket.max;           
            if (sum + delta >= result)
                return;
                
            int prevMax = bucket.max;    
            bucket.max = num;
            bucket.size++; 

            dfs(nums, index + 1, sum + delta, buckets, bucketSize);
            
            bucket.size--;
            bucket.max = prevMax;
        }
    }

    class Bucket {
        int size = 0;
        int max = 0;
        Bucket(){}
    }    
}


